package com.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * 208. 实现 Trie (前缀树)
 * Trie，又称前缀树或字典树，是一棵有根树
 * 使用HashMap来动态分叉
 *
 * DFS 递归 版本, dfs 普遍会更快一点点
 *
 * @author fy
 * @date 2022/4/19 9:54
 */
public class Solution208_2 {

    class Trie {

        // 类, 属性, 构造方法都可以private, 外部类可以访问到
        private class Node {
            private boolean isWord;
            private Map<Character, Node> next;

            private Node() {
                this(false);
            }

            private Node(boolean isWord) {
                this.isWord = isWord;
                this.next = new HashMap<>();
            }
        }

        private Node root;

        public Trie() {
            root = new Node();
        }

        public void insert(String word) {
            dfsInsert(word, 0, root);
        }

        public boolean search(String word) {
            Node node = dfsSearch(word, 0, root);
            return node != null && node.isWord;
        }

        public boolean startsWith(String prefix) {
            return dfsSearch(prefix, 0, root) != null;
        }

        /**
         * 递归插入构建Trie
         *
         * @param word
         * @param index
         * @param node
         */
        private void dfsInsert(String word, int index, Node node) {
            int len = word.length();
            char ch = word.charAt(index);
            if (node.next.get(ch) == null) {
                node.next.put(ch, new Node());
            }
            node = node.next.get(ch);
            if (len - 1 == index) {
                node.isWord = true;
                return;
            }
            dfsInsert(word, index + 1,  node);
        }

        /**
         * 递归查找前缀
         *
         * @param prefix
         * @return
         */
        private Node dfsSearch(String prefix, int index, Node node) {
            char ch = prefix.charAt(index);
            if (index == prefix.length() - 1) {
                return node.next.get(ch);
            }
            if (node.next.get(ch) == null) {
                return null;
            }
            return dfsSearch(prefix, index + 1, node.next.get(ch));
        }

    }

}
